/**
 * 贪心
 * @param {number[]} nums
 * @return {number}
 */
export var maxSubArray = function (nums) {
  let ans = -Infinity
  let tempSum = 0
  for (let i = 0; i < nums.length; i++) {
    tempSum += nums[i]
    ans = Math.max(ans, tempSum)
    if (tempSum < 0) tempSum = 0 // 遇到负数重新计算tempSum
  }
  return ans
}

/**
 * 动态规划
 * @param {number[]} nums
 * @return {number}
 */
export var maxSubArray2 = function (nums) {
  const dp = [nums[0]]
  let ans = nums[0]
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
    ans = Math.max(ans, dp[i])
  }
  return ans
}

/** 二分法，线段树 **/
function Status(l, r, m, i) {
  this.lSum = l
  this.rSum = r
  this.mSum = m
  this.iSum = i
}

const pushUp = (l, r) => {
  const iSum = l.iSum + r.iSum
  const lSum = Math.max(l.lSum, l.iSum + r.lSum)
  const rSum = Math.max(r.rSum, r.iSum + l.rSum)
  const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum)
  return new Status(lSum, rSum, mSum, iSum)
}

const getInfo = (a, l, r) => {
  if (l === r) {
    return new Status(a[l], a[l], a[l], a[l])
  }
  const m = (l + r) >> 1
  const lSub = getInfo(a, l, m)
  const rSub = getInfo(a, m + 1, r)
  return pushUp(lSub, rSub)
}

export var maxSubArray3 = function (nums) {
  return getInfo(nums, 0, nums.length - 1).mSum
}
